<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <meta charset="utf-8" />
    <title>线性规划</title>
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>问题的提出</h2>

<p class="question">
	线性规划问题的<b>一般形式</b>为
	<span class="formula">
		最大化 (最小化) `z = sum_(j=1)^n c_j x_j`, 满足<br/>
		`sum_(j=1)^n a_(i j) x_j le (=,ge) b_i`, `quad i = 1, cdots, m`,<br/>
		`x_j ge 0`, `quad j in S sube {1, 2, cdots, n}`.
	</span>
	<b>标准形式</b>为
	<span class="formula">
		最大化 `z = sum_(j=1)^n c_j x_j`, 满足<br/>
		`sum_(j=1)^n a_(i j) x_j le b_i`, `quad i = 1, cdots, m`,<br/>
		`x_j ge 0`, `quad j = 1, cdots, n`.
	</span>
	引入记号
	<span class="formula">
		`bm A = [a_11, a_12, cdots, a_(1n);
				 a_21, a_22, cdots, a_(2n);
				 vdots, vdots, , vdots;
				 a_(m1), a_(m2), cdots, a_(m n)]`,
		`bm b = [b_1;b_2;vdots;b_m]`,
		`bm c = [c_1;c_2;vdots;c_n]`,
		`bm x = [x_1;x_2;vdots;x_n]`,
		`bb 0 = [0; 0; vdots; 0]`,
	</span>
	线性规划的标准形式可以写成更加紧凑的形式:
	<span class="formula">
		`max z = {:bm c:}^T bm x`,<br/>
		`bm (A x) le bm b`,<br/>
		`bm x ge bb 0`.
	</span>
	其中不等号表示向量的每一分量均满足该不等式.
	为了便于使用下文提到的单纯形法求解线性规划, 再引入<b>松弛形式</b>,
	它与标准形式的区别在于将 "`le`" 换成了 "`=`":
	<span class="formula">
		`max z = {:bm c:}^T bm x`,<br/>
		`bm (A x) = bm b`,<br/>
		`bm x ge bb 0`.
	</span>
	因此, 三元组 `(bm A, bm b, bm c)` 就完全决定了一个线性规则的标准形式
	(或松弛形式).
</p>

<ul class="definition">
	我们介绍 (标准形式) 线性规划的相关术语.
	<li><b>目标函数</b> `z={:bm c:}^T bm x`, 它是 `bm x` 的线性函数;</li>
	<li><b>约束条件</b> 包括线性约束 `bm(A x) le bm b`
		和非负约束 `bm x ge bb 0`;</li>
	<li><b>可行解</b> 是指满足约束条件的某个 `bm x`,
		全体可行解的集合称为<b>可行域</b>;</li>
	<li><b>最优解</b> 使目标函数取得最大值的可行解;</li>
</ul>

<ol class="algorithm">
	<b>线性规划的标准化</b>
	依次进行以下步骤来将线性规划问题化为与原问题等价的标准形式:
	<li>若要求 `z` 最小化, 可令 `z' = -z = -{:bm c:}^T bm x`,
		从而转化为将 `z'` 最大化;</li>
	<li>若存在无约束变量 `x_i`, 可引入新变量 `x_j, x_k ge 0`,
		再令 `x_i = x_j - x_k`,
	</li>
	<li>将线性约束化为 "`le`" 的形式.
		具体做法是将所有线性等式 `sum_(j=1)^n a_(i j) x_j = b_i`
		用等价的两个不等式 `sum_(j=1)^n a_(i j) x_j le b_i` 和
		`sum_(j=1)^n a_(i j) ge b_i` 代替, 然后在所有线性不等式
		`sum_(j=1)^n a_(i j) x_j ge b_i` 两边同乘以 `-1`.
	</li>
	<b>将线性规划标准形化为松弛形</b>
	为每个线性约束引入一个变量
	<span class="formula">
		`x_(n+i) = b_i - sum_(j=1)^n a_(i j) x_j`,
		`quad x_(n+i) ge 0`,
		`quad i = 1, cdots, m`,
	</span>
	称为<b>松弛变量</b>. 这个变量反映了不等式两边的差, 亦即约束条件的
	"松紧" 程度. 用上面的 `m` 个等式代替原线性约束, 就得到等价的松弛形式.
</ol>

<h2>单纯形法</h2>

<p>	单纯形法 (simplex method) 是 G. Dantzig 于 1947 年提出的经典算法,
	它是一种有效求解线性规划的代数算法.
	算法在每一步中从单纯形的一个顶点移动到目标值不小于当前值的相邻顶点.
	如果当前值达到局部最优, 即所有相邻顶点的目标值不大于当前值时,
	算法终止. 可以证明, 此时目标值实际已达到全局最优.
	下面通过具体实例来介绍单纯形法.
</p>

<p class="example">
	求解线性规划
	<span class="formula">
		`max z = 3 x_1 + x_2 + 2 x_3`,<br/>
		`x_1 + x_2 + 3 x_3 le 30`,<br/>
		`2 x_1 + 2 x_2 + 5 x_3 le 24`,<br/>
		`4 x_1 + x_2 + 2 x_3 le 36`,<br/>
		`x_1, x_2, x_3 ge 0`.
	</span>
</p>

<p class="solution">
	由于我们对线性规划标准形的约定, 原问题可简记为
	<span class="formula">
		`z = 3 x_1 + x_2 + 2 x_3`,<br/>
		`x_1 + x_2 + 3 x_3 le 30`,<br/>
		`2 x_1 + 2 x_2 + 5 x_3 le 24`,<br/>
		`4 x_1 + x_2 + 2 x_3 le 36`.
	</span>
	现在引入松弛变量, 问题化为
	<span class="formula">
		`z = 3 x_1 + x_2 + 2 x_3`,<br/>
		`x_4 = 30 - x_1 - x_2 - 3 x_3`,<br/>
		`x_5 = 24 - 2 x_1 - 2 x_2 - 5 x_3`,<br/>
		`x_6 = 36 - 4 x_1 - x_2 - 2 x_3`.
	</span>
	如果令等号右边的所有变量等于零, 就得到一个解 `(0, 0, 0, 30, 24, 36)`,
	对应的 `z = 0`.
	我们把等号左边的变量称为<b>基变量</b>, 右边的称为<b>非基变量</b>.
	观察 `z` 的表达式, 因为 `x_1, x_2, x_3` 前的系数为正,
	所以只要增大其中任一变量 (比如 `x_1`), `z` 的值就能增大. 但 `x_1`
	的增大受到非负约束的限制, 我们必须保证 `x_4, x_5, x_6` 非负, 即
	<span class="formula">
		`x_1 le 30`, `quad 2 x_1 le 24`, `quad 4 x_1 le 36`.
	</span>
	其中最紧的约束是 `x_1 le 9`. 因此最多将 `x_1` 增大到 `9`, 而这时 `x_6
	= 0`. 我们把增大一个变量,
	而另一变量减小到零的这种操作称作一次<b>旋转</b>, 增大的变量 (`x_1`)
	称为<b>换入变量</b>, 减小到零的变量称为<b>换出变量</b>. 现在将
	<span class="formula">
		`x_1 = 9 - x_2/4 - x_3/2 - x_6/4`
	</span>
	代入各式, 问题化为
	<span class="formula">
		`z = 27 + x_2/4 + x_3/2 - (3 x_6)/4`,<br/>
		`x_1 = 9 - x_2/4 - x_3/2 - x_6/4`,<br/>
		`x_4 = 21 - (3 x_2)/4 - (5 x_3)/2 + x_6/4`,<br/>
		`x_5 = 6 - (3 x_2)/2 - 4 x_3 + x_6/2`.
	</span>
	依照前面的做法, 令非基变量等于零, 得到解
	`(9, 0, 0, 21, 6, 0)` 和 `z = 27`. 旋转操作确实让 `z` 的值增加了!<br/>
	继续观察 `z` 的表达式, `x_2, x_3` 的系数仍为正, 我们选择 `x_2`
	为换入变量, 通过
	<span class="formula">
		`x_2/4 le 9`, `quad (3 x_2)/4 le 21`, `quad (3 x_2)/2 le 6`
	</span>
	确定第三个约束为最紧, 因此换出 `x_5`:
	<span class="formula">
		`z = 28 - x_3/6 - x_5/6 - (2 x_6)/3`,<br/>
		`x_1 = 8 + x_3/6 + x_5/6 - x_6/3`,<br/>
		`x_2 = 4 - (8 x_3)/3 - (2 x_5)/3 + x_6/3`,<br/>
		`x_4 = 18 - x_3/2 + x_5/2`.
	</span>
	令非基变量等于零, 得到解 `(8, 4, 0, 18, 0, 0)` 和 `z = 28`.
	由于 `z` 的表达式中所有系数都为负, 此时不论换入哪个变量都不可能增加
	`z` 的值, 因此我们断定最优解已经得到.
</p>

<div class="solution">
	将前一种解法用矩阵再现.  记
	<span class="formula">
		`bm A = [1, 1, 3; 2, 2, 5; 4, 1, 2]`,
		`bm b = [30; 24; 36]`,
		`bm c = [3; 1; 2]`,
	</span>
	原问题即为求解标准形线性规划 `(bm A, bm b, bm c)`.
	将松弛形式写成常数项在右边, 其余各项在左边的形式:
	<span class="formula">
		`-3 x_1 - x_2 - 2 x_3 + z = 0`,<br/>
		`x_1 + x_2 + 3 x_2 + x_4 = 30`,<br/>
		`2 x_1 + 2 x_2 + 5 x_3 + x_5 = 24`,<br/>
		`4 x_1 + x_2 + 2 x_3 + x_6 = 36`.
	</span>
	提取系数矩阵 `(-bm c, bb 0, 0; bm A, bm E, bm b)`:
	<span class="formula">
		`{: z; x_4; x_5; x_6 :}`
		`[-3, -1, -2, 0, 0, 0;
		  1, 1, 3, 1, 0, 0;
		  2, 2, 5, 0, 1, 0;
		  (4), 1, 2, 0, 0, 1]`
		`{: 0; 30; 24; 36 :}`
	</span>
	当前解为 `(0, 0, 0, 30, 24, 36)`, `z = 0`.
	在矩阵的 `z` 行中任取系数为负的一列, 如第一列, 这意味着选择 `x_1`
	为换入变量. 用 `bm b` 中的各行除以矩阵第一列的各行, 得到
	<span class="formula">
		`30/1 = 30`, `quad 24/2 = 12`, `quad 36/4 = 9`.
	</span>
	其中 `x_6` 行的商等于 `9` 为最小, 因此 `x_6` 为换出变量.
	下面执行旋转操作, 只需将矩阵的 `x_6` 行乘以系数 `1//4`,
	使得该行的第一列化为 `1`, 再将 `x_6` 行的合适倍数加到其余各行,
	使得第一列中除 `x_6` 行等于 `1` 外, 其余各元素都等于 `0`.
	接着, 用新的变量 `x_1` 标记原来的 `x_6` 行:
	<span class="formula">
		`{: z; x_4; x_5; x_1 :}`
		`[0, -1//4, -1//2, 0, 0, 3//4;
		  0, 3//4, 5//2, 1, 0, -1//4;
		  0, (3//2), 4, 0, 1, -1//2;
		  1, 1//4, 1//2, 0, 0, 1//4]`
		`{: 27; 21; 6; 9 :}`
	</span>
	当前解为 `(9, 0, 0, 21, 6, 0)`, `z = 27`.
	`z` 行中仍有负系数, 算法继续. 选取换入变量 `x_2`, 因为
	<span class="formula">
		`21/(3//4)`, `quad 6/(3//2)`, `quad 9/(1//4)`
	</span>
	中, 第二个为最小, 我们选择换出相应的 `x_5`:
	<span class="formula">
		`{: z; x_4; x_2; x_1 :}`
		`[0, 0, 1//6, 0, 1//6, 2//3;
		  0, 0, 1//2, 1, -1//2, 0;
		  0, 1, 8//3, 0, 2//3, -1//3;
		  1, 0, -1//6, 0, -1//6, 1//3]`
		`{: 28; 18; 4; 8 :}`
	</span>
	当前解为 `(8, 4, 0, 18, 0, 0)`, `z = 28`. 由于 `z` 行中已无负系数,
	最优解已得到, 算法终止.
</div>

<p class="example">
	解线性规划
	<span class="formula">
		`max z = 2 x_1 + 3 x_2`,<br/>
		`x_1 + 2 x_2 le 8`,<br/>
		`4 x_1 le 16`,<br/>
		`4 x_2 le 12`,<br/>
		`x_1, x_2 ge 0`.
	</span>
</p>

<p class="solution">
	矩阵计算过程如下:
	<span class="formula">
		`{: z; x_3; x_4; x_5 :}`
		`[-2, -3, 0, 0, 0;
		  1, 2, 1, 0, 0;
		  (4), 0, 0, 1, 0;
		  0, 4, 0, 0, 1]`
		`{: 0; 8; 16; 12 :}`<br/>
		`8/1 = 8`, `quad 16/4 = 4`, `quad 12/0 = oo`.
	</span>
	<span class="formula">
		`{: z; x_3; x_1; x_5 :}`
		`[0, -3, 0, 1//2, 0;
		  0, (2), 1, -1//4, 0;
		  1, 0, 0, 1//4, 0;
		  0, 4, 0, 0, 1]`
		`{: 8; 4; 4; 12 :}`<br/>
		`4/2 = 2`, `quad 4/0 = oo`, `quad 12/4 = 3`.
	</span>
	<span class="formula">
		`{: z; x_2; x_1; x_5 :}`
		`[0, 0, 3//2, 1//8, 0;
		  0, 1, 1//2, -1//8, 0;
		  1, 0, 0, 1//4, 0;
		  0, 0, -2, -1//2, 1]`
		`{: 14; 2; 4; 4 :}`<br/>
	</span>
	`z` 行系数非负, 算法终止. 最优解为 `(4, 2, 0, 0, 4)`, `z = 14`.
</p>

<p class="example">
  [来自 无懈可击99]
  求 `|x-3y+2|+|x+y|+|x|` 的最小值.
</p>

<p class="solution">
  因为绝对值函数 `|x| = max(x, -x)`, 问题化为线性规划
  <span class="formula">
    `min x3+x4+x5`,<br>
    `x-3y+2 le x_3`,<br>
    `-x+3y-2 le x_3`,<br>
    `x+y le x_4`,<br>
    `-x-y le x_4`,<br>
    `x le x_5`,<br>
    `-x le x_5`,<br>
  </span>
  其中各变量取无约束的实值.
</p>

<p class="solution">
  记 `f = |x-3y+2|+|x+y|+|x|`, 熟知最值必在边界上取得:
  <span class="formula">
    `x = 0 or x = -y or 3y - x = 2`
  </span>
  由后两个等式得到: `y = 0.5`, `x = -0.5`, `f = 0.5`.  和
  <span class="formula">
    `x = 0, y = 0  rArr  f = 2`,<br>
    `x = 0, 3y - x = 2  rArr  f = 2//3`.
  </span>
  比较知, `f` 的最小值是 `1//2`.
</p>

<div class="playground" type="textarea" value2="min x3+x4+x5
x1-3x2-x3 <= -2
-x1+3x2-x3 <= 2
x1+x2-x4 <= 0
-x1-x2-x4 <= 0
x1-x5 <= 0
-x1-x5 <= 0
free x1 x2 x3 x4 x5" value="max 3x - y - z
x - 2y + z <= 11
4x - y - 2z <= -3
-2x + z <= 1
2x - z <= -1">

<p>说明:
第一行指定目标函数.
接下来 m 行指定约束, 可以是等式 (=) 或不等式 (&lt;=, &gt;=), 注意常数必须放在右边, 其余项放在左边.
默认每个变量都取非负实数, 如果某些变量可以取全体实数, 则将它们在最后一行列出, 如: <code>free x y z</code>.
</p>
<script type="text">
module.exports = function lpSolve (str) {
  return LP.from(str).solveInfo()
}
</script>
</div>


<h3>单纯形法的正确性</h3>

<ul class="definition">
	<li><b>基</b> 是指 `bm A` 中线性无关的 `m` 个列向量组成的向量组,
		其中每个向量 `bm A_i` 称为一个<b>基向量</b>, 相应的 `x_i`
		称为一个<b>基变量</b>, 而其余的 `x_j` 称为<b>非基变量</b>.
	</li>
	<li><b>基解</b>
		注意松弛形中的约束等式 `bm (A x) = bm b`.
		若 `bm A` 的秩为 `m`, 因 `m lt n`, 方程组 `bm (A x) = bm b`
		有无穷多解. 不妨设 `bm A` 的前 `m` 列组成一个基, 则方程组化为
		<span class="formula">
			`sum_(j=1)^m {:bm A:}_j^T x_j
			= bm b - sum_(j=m+1)^n {:bm A:}_j^T x_j`.
		</span>
		每取定一组 `(x_(m+1), cdots, x_n)` 的值,
		相应地就能得到方程组的一个解. 特别令非基变量 `x_(m+1) = x_(m+2)
		= cdots = x_n = 0`, 就得到方程组的特解:
		<span class="formula">
			`bm x = (x_1, x_2, cdots, x_m, 0, cdots, 0)^T`,
		</span>
		称为一个<b>基解</b>. 由以上讨论知方程组的基解与基一一对应.
		通常情形, 基解中的非零分量数等于 `m`; 当它小于 `m` 时,
		线性规划问题出现退化.
	</li>
	<li><b>基可行解</b> 是指满足非负约束 `bm x ge bb 0` 的基解,
		由于基解必然满足等式约束, 基可行解必为可行解.
		对应于基可行解的基称为<b>可行基</b>.
	</li>
</ul>

本节的几个命题刻画了线性规划的解的性态.

<p class="definition">
	设 `D` 是 `n` 维 Euclid 空间的子集, 若对任意 `bm x, bm y in D`,
	`D` 包含了它们连线上的任一点:
	<span class="formula">
		`t bm x + (1-t) bm y in D`, `quad t in (0,1)`,
	</span>
	则称 `D` 是<b>凸集</b>.
	若 `bm x in D`, 且不存在 `bm y, bm z in D` 使得
	<span class="formula">
		`bm x = t bm y + (1-t) bm z`, `quad t in (0, 1)`,
	</span>
	则称 `bm x` 是凸集 `D` 的<b>顶点</b>.
</p>

<p class="lemma">
	线性规划的可行解 `bm x` 为基可行解当且仅当 `bm x`
	的非零分量对应的列向量组线性无关.
</p>

<p class="lemma">
	`n` 维 Euclid 空间中的有界凸集 `D` 中任意一点 `bm x` 可表示为 `D`
	的顶点 `bm x_1, bm x_2, cdots, bm x_k` 的<b>凸组合</b>,
	即存在实数 `t_1, t_2, cdots, t_k in [0, 1]` 满足 `sum_(i=1)^k t_i
	= 1`, 使得
	<span class="formula">
		`bm x = sum_(i=1)^k t_i bm x_i`.
	</span>
	特别当 `0 lt t_i lt 1` 时, 称为严格凸组合.
</p>

<p class="proposition">
	线性规划问题的可行域
	<span class="formula">
		`D = {bm x: sum_(i=1)^n bm A_i x_i = bm b, bm x ge 0}`
	</span>
	是凸集.
</p>

<p class="proposition">
	线性规划的基可行解 `bm x` 与可行域的顶点一一对应.
</p>

<p class="proposition">
	若可行域有界, 线性规划的目标函数一定能在基可行域的某个顶点上达到最大.
</p>

<p class="corollary">
	若目标函数在多个顶点处达到最大值,
	则它在这些顶点的凸组合上也达到最大值.
</p>

<script src="../../js/note.js?type=math"></script>
<script src="../../js/playground.js"></script>
<script src="../../code/lp.js"></script>
</body>
</html>
